package org.codetranslators.common.optimization;

import org.codetranslators.common.Edge;
import org.codetranslators.common.DiGraph;
import org.codetranslators.common.Node;
import org.codetranslators.common.DominatorTree;
import org.codetranslators.common.DominatorTreeNode;

import java.util.Iterator;
import java.util.Vector;
import java.util.HashMap;
import java.util.HashSet;

public class LengauerTarjanTestMain {

	public static void main(String args[]){
		
		LengauerTarjanTestMain lttm = new LengauerTarjanTestMain();
		//Node startNode = new Node("A");
		//Node startNode = new Node("B0");
		Node startNode = new Node("1");
		DiGraph graph = lttm.createGraph(startNode);
		
		DominatorCalculationContext dominatorCalculationContext = 
			new DominatorCalculationContext(graph, startNode);
		dominatorCalculationContext.setLengauerTarjan();
		
		DominatorTree dominatorTree = dominatorCalculationContext.getDominatorTree();
		DominatorTreeNode dominatorTreeNode = dominatorTree.getDominatorTreeRoot();
		System.out.println("DOMINATOR TREE: ");
		dominatorTreeNode.display();
		
		// Calculate the dominance frontiers
		HashMap dominanceFrontiers = new HashMap();
		int numGraphNodes = graph.getNumNodes();
		for(int i = 0; i < numGraphNodes; i++){
			Node node = (Node) graph.getNode(i);
			Vector predecessors = node.getPredecessors();
			int numPreds = predecessors.size();
			if(numPreds > 1){
				// This node has more than predecessor
				Node immediateDominator = dominatorTree.getParentInTree(node);
				for(int j = 0; j < numPreds; j++){
					Node predecessor = (Node) predecessors.elementAt(j);
					Node runner = predecessor;
					while(runner != immediateDominator){
						//if(runner == node) break;
						addToDominanceFrontier(dominanceFrontiers, runner, node);
						runner = dominatorTree.getParentInTree(runner);
					}
				}
			}
		}
		
		// Display the dominance frontiers
		System.out.println("DOMINANCE FRONTIERS: ");
		for(int j = 0; j < numGraphNodes; j++){
			Node node = (Node) graph.getNode(j);
			System.out.print("Node " + node.getName() + ": ");
			HashSet members = (HashSet) dominanceFrontiers.get(node);
			if(members != null){
				Iterator iter = members.iterator();
				while(iter.hasNext()){
					Node mem = (Node) iter.next();
					System.out.print(mem.getName() + ", ");
				}
			}
			System.out.println("");
		}
	}
	
	public static void addToDominanceFrontier(HashMap dominanceFrontiers, Node node, Node frontierMember){
		HashSet members = (HashSet) dominanceFrontiers.get(node);
		if(members == null) members = new HashSet();
		members.add(frontierMember);
		dominanceFrontiers.put(node, members);
	}
	
	public DiGraph createGraph(Node startNode){
		DiGraph graph = new DiGraph();
		/*
		// Create the nodes first
		Node nodeB = new Node("B");
		Node nodeC = new Node("C");
		Node nodeD = new Node("D");
		Node nodeE = new Node("E");
		Node nodeF = new Node("F");
		Node nodeG = new Node("G");
		Node nodeH = new Node("H");
		Node nodeI = new Node("I");
		Node nodeJ = new Node("J");
		Node nodeK = new Node("K");
		Node nodeL = new Node("L");
		Node nodeM = new Node("M");
		
		// Add the nodes to the graph
		graph.addNode(startNode);
		graph.addNode(nodeB);
		graph.addNode(nodeC);
		graph.addNode(nodeD);
		graph.addNode(nodeE);
		graph.addNode(nodeF);
		graph.addNode(nodeG);
		graph.addNode(nodeH);
		graph.addNode(nodeI);
		graph.addNode(nodeJ);
		graph.addNode(nodeK);
		graph.addNode(nodeL);
		graph.addNode(nodeM);
		
		// Create the links
		Edge edgeAB = new Edge(startNode, nodeB);
		Edge edgeAC = new Edge(startNode, nodeC);
		Edge edgeBD = new Edge(nodeB, nodeD);
		Edge edgeBG = new Edge(nodeB, nodeG);
		Edge edgeDF = new Edge(nodeD, nodeF);
		Edge edgeDG = new Edge(nodeD, nodeG);
		Edge edgeFI = new Edge(nodeF, nodeI);
		Edge edgeFK = new Edge(nodeF, nodeK);
		Edge edgeIL = new Edge(nodeI, nodeL);
		Edge edgeKL = new Edge(nodeK, nodeL);
		Edge edgeGJ = new Edge(nodeG, nodeJ);
		Edge edgeJI = new Edge(nodeJ, nodeI);
		Edge edgeCE = new Edge(nodeC, nodeE);
		Edge edgeCH = new Edge(nodeC, nodeH);
		Edge edgeEC = new Edge(nodeE, nodeC);
		Edge edgeEH = new Edge(nodeE, nodeH);
		Edge edgeHM = new Edge(nodeH, nodeM);
		Edge edgeLB = new Edge(nodeL, nodeB);
		Edge edgeLM = new Edge(nodeL, nodeM);
		
		// Add the edges to the graph
		graph.addDirectedEdge(edgeAB, startNode, nodeB);
		graph.addDirectedEdge(edgeAC, startNode, nodeC);
		graph.addDirectedEdge(edgeBD, nodeB, nodeD);
		graph.addDirectedEdge(edgeBG, nodeB, nodeG);
		graph.addDirectedEdge(edgeDF, nodeD, nodeF);
		graph.addDirectedEdge(edgeDG, nodeD, nodeG);
		graph.addDirectedEdge(edgeGJ, nodeG, nodeJ);
		graph.addDirectedEdge(edgeFI, nodeF, nodeI);
		graph.addDirectedEdge(edgeFK, nodeF, nodeK);
		graph.addDirectedEdge(edgeIL, nodeI, nodeL);
		graph.addDirectedEdge(edgeKL, nodeK, nodeL);
		graph.addDirectedEdge(edgeJI, nodeJ, nodeI);
		graph.addDirectedEdge(edgeCE, nodeC, nodeE);
		graph.addDirectedEdge(edgeCH, nodeC, nodeH);
		graph.addDirectedEdge(edgeEC, nodeE, nodeC);
		graph.addDirectedEdge(edgeEH, nodeE, nodeH);
		graph.addDirectedEdge(edgeHM, nodeH, nodeM);
		graph.addDirectedEdge(edgeLB, nodeL, nodeB);
		graph.addDirectedEdge(edgeLM, nodeL, nodeM);
		


		//Create the nodes first
		Node nodeB1 = new Node("B1");
		Node nodeB2 = new Node("B2");
		Node nodeB3 = new Node("B3");
		Node nodeB4 = new Node("B4");
		Node nodeB5 = new Node("B5");
		Node nodeB6 = new Node("B6");
		Node nodeB7 = new Node("B7");
		
		// Add the nodes to the graph
		graph.addNode(startNode);
		graph.addNode(nodeB1);
		graph.addNode(nodeB2);
		graph.addNode(nodeB3);
		graph.addNode(nodeB4);
		graph.addNode(nodeB5);
		graph.addNode(nodeB6);
		graph.addNode(nodeB7);
		
		// Create the links
		Edge edge01 = new Edge(startNode, nodeB1);
		Edge edge12 = new Edge(nodeB1, nodeB2);
		Edge edge27 = new Edge(nodeB2, nodeB7);
		Edge edge13 = new Edge(nodeB1, nodeB3);
		Edge edge34 = new Edge(nodeB3, nodeB4);
		Edge edge35 = new Edge(nodeB3, nodeB5);
		Edge edge46 = new Edge(nodeB4, nodeB6);
		Edge edge56 = new Edge(nodeB5, nodeB6);
		Edge edge67 = new Edge(nodeB6, nodeB7);
		Edge edge71 = new Edge(nodeB7, nodeB1);
		
		// Add the edges to the graph
		graph.addDirectedEdge(edge01, startNode, nodeB1);
		graph.addDirectedEdge(edge12, nodeB1, nodeB2);
		graph.addDirectedEdge(edge27, nodeB2, nodeB7);
		graph.addDirectedEdge(edge13, nodeB1, nodeB3);
		graph.addDirectedEdge(edge34, nodeB3, nodeB4);
		graph.addDirectedEdge(edge35, nodeB3, nodeB5);
		graph.addDirectedEdge(edge46, nodeB4, nodeB6);
		graph.addDirectedEdge(edge56, nodeB5, nodeB6);
		graph.addDirectedEdge(edge67, nodeB6, nodeB7);
		graph.addDirectedEdge(edge71, nodeB7, nodeB1);
		*/
		
//		 Create the nodes first
		Node node2 = new Node("2");
		Node node3 = new Node("3");
		Node node4 = new Node("4");
		Node node5 = new Node("5");
		Node node6 = new Node("6");
		Node node7 = new Node("7");
		Node node8 = new Node("8");
		Node node9 = new Node("9");
		Node node10 = new Node("10");
		Node node11 = new Node("11");
		Node node12 = new Node("12");
		Node node13 = new Node("13");
		
		// Add the nodes to the graph
		graph.addNode(startNode);
		graph.addNode(node2);
		graph.addNode(node3);
		graph.addNode(node4);
		graph.addNode(node5);
		graph.addNode(node6);
		graph.addNode(node7);
		graph.addNode(node8);
		graph.addNode(node9);
		graph.addNode(node10);
		graph.addNode(node11);
		graph.addNode(node12);
		graph.addNode(node13);
		
		// Create the links
		Edge edge12 = new Edge(startNode, node2);
		Edge edge19 = new Edge(startNode, node9);
		Edge edge23 = new Edge(node2, node3);
		Edge edge34 = new Edge(node3, node3);
		Edge edge413 = new Edge(node4, node13);
		Edge edge910 = new Edge(node9, node10);
		Edge edge911 = new Edge(node9, node11);
		Edge edge1012 = new Edge(node10, node12);
		Edge edge1112 = new Edge(node11, node12);
		Edge edge1213 = new Edge(node12, node13);
		Edge edgeG15 = new Edge(startNode, node5);
		Edge edge56 = new Edge(node5, node6);
		Edge edge57 = new Edge(node5, node7);
		Edge edge68 = new Edge(node6, node8);
		Edge edge78 = new Edge(node7, node8);
		Edge edge813 = new Edge(node8, node13);
		Edge edge85 = new Edge(node8, node5);
		Edge edge64 = new Edge(node6, node4);
		Edge edge712 = new Edge(node7, node12);
		Edge edge33 = new Edge(node3, node3);
		
		// Add the edges to the graph
		graph.addDirectedEdge(edge12,startNode, node2);
		graph.addDirectedEdge(edge19,startNode, node9);
		graph.addDirectedEdge(edge23,node2, node3);
		graph.addDirectedEdge(edge34,node3, node4);
		graph.addDirectedEdge(edge413,node4, node13);
		graph.addDirectedEdge(edge910,node9, node10);
		graph.addDirectedEdge(edge911,node9, node11);
		graph.addDirectedEdge(edge1012,node10, node12);
		graph.addDirectedEdge(edge1112,node11, node12);
		graph.addDirectedEdge(edge1213,node12, node13);
		graph.addDirectedEdge(edgeG15,startNode, node5);
		graph.addDirectedEdge(edge56,node5, node6);
		graph.addDirectedEdge(edge57,node5, node7);
		graph.addDirectedEdge(edge68,node6, node8);
		graph.addDirectedEdge(edge78,node7, node8);
		graph.addDirectedEdge(edge813,node8, node13);
		graph.addDirectedEdge(edge85,node8, node5);
		graph.addDirectedEdge(edge64,node6, node4);
		graph.addDirectedEdge(edge712,node7, node12);
		graph.addDirectedEdge(edge33,node3, node3);
		
		return graph;
	}
}
